﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/two-sum/
/*
题目描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
*/

// 方法1——暴力法
/*
思路：
对于每一个元素，都向它后面遍历，如果在它后边找到一个等于target = nums[i] 的元素
就返回他们两的下标
*/

// 有了以上思路，那我们写起代码来也就是水到渠成了：
int* twoSum1	(int* nums, int numsSize, int target, int* returnSize) {
	assert(nums && returnSize);
	int i = 0;
	int j = 0;
	for (i = 0; i < numsSize - 1; i++) {
		for (j = i + 1; j < numsSize; j++) {
			if (nums[i] + nums[j] == target) {
				nums[0] = i;
				nums[1] = j;
				*returnSize = 2;
			}
		}
	}
	return nums;
}
// 时间复杂度：O(n^2)，n为数组元素个数。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法2——先排序后二分
/*
思路：
先拷贝一份数组存入数组temp中，然后对拷贝的数组进行排序，排序后再使用二分查找。
但对于temp[i]我们还要分情况讨论：
当temp[i] <= target / 2时，则说明另一个数在temp[i]的后面，这时候应该使left = i + 1,right = numsSize - 1;
当temp[i] > target / 2时，则说明另一个数在temp的前面，这时候应该使left = 0， right = i;
中间如果找到了，就直接返回true，如果一直找不到，就返回false。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
// 先写一个用于比较两个整型的函数
int cmp_int(const void* p1, const void* p2) {
	assert(p1 && p2);
	return *((int*)p1) - *((int*)p2);
}
int* twoSum2(int* nums, int numsSize, int target, int* returnSize) {
	assert(nums && returnSize);
	int* temp = (int*)malloc(numsSize * sizeof(int));
	int i = 0;
	// 拷贝数组nums
	for (i = 0; i < numsSize; i++) {
		temp[i] = nums[i];
	}
	// 对temp进行排序
	qsort(nums, numsSize, sizeof(nums[0]), cmp_int);
	// 对每个元素在进行二分查找
	int left = 0;
	int right = 0;
	int mid = 0;
	int ans1 = 0;
	int ans2 = 0;
	for (i = 0; i < numsSize - 1; i++) {
		if (temp[i] <= target / 2) {
			left = i + 1;
			right = numsSize - 1;
			while (left < right) {
				mid = left + (right - left) / 2;
				if (temp[mid] < target - temp[i]) {
					right = mid - 1;
				}
				else if (temp[mid] > target - temp[i]) {
					left = mid + 1;
				}
				else {
					ans1 = temp[i];
					ans2 = temp[mid];
				}
			}
		}
		else {
			left = 0;
			right = i - 1;
			while (left < right) {
				mid = left + (right - left) / 2;
				if (temp[mid] < target - temp[i]) {
					right = mid - 1;
				}
				else if (temp[mid] > target - temp[i]) {
					left = mid + 1;
				}
				else {
					ans1 = temp[i];
					ans2 = temp[mid];
				}
			}
		}
	}
	for (i = 0; i < numsSize; i++) {
		if (nums[i] == ans1) {
			nums[0] = i;
		}
		else if (nums[i] == ans2) {
			nums[1] = i;
		}
	}
	*returnSize = 2;
	return nums;
}
